package Algorithm;

import Structure.Graph;
import Structure.GraphGenerator;
import Structure.Node;

import java.util.*;

/**
 * @Author: ylc
 * @Description:深度优先遍历
 * @Date Created in 2022-06-06 18:35
 */
public class Dfs {
    public static void dfs(Node node){
        if(node == null){
            return ;
        }
        Deque<Node> stack = new ArrayDeque<>();
        Set<Node> set = new HashSet<>();
        stack.push(node);
        set.add(node);
        System.out.print(node.value + " ");
        while(!stack.isEmpty()){
            Node curNade = stack.pop();
            for (Node next :
                    curNade.nexts) {
                if (!set.contains(next)){
                    stack.push(curNade);
                    stack.push(next);
                    set.add(next);
                    System.out.print(next.value + " ");
                    break;
                }
            }
        }
    }

    public static void main(String[] args) {
        Graph graph = create();
        dfs(graph.nodes.get(1));
    }

    public static Graph create(){
        int[][] arr = {
                {1,1,2},{1,2,1},
                {1,1,3},{1,3,1},
                {1,1,4},{1,4,1},
                {1,2,3},{1,3,2},
                {1,3,4},{1,4,3},
                {1,2,5},{1,5,2},
                {1,4,5},{1,5,4}

        };

        return GraphGenerator.generateGraph(arr);
    }

}
